import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName LC22
 * 括号生成
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * @Author ykx
 * @Date 2024/3/6 12:31
 * @Version 1.0
 */
public class LC22 {

    public static void main(String[] args) {
        LC22 lc22 = new LC22();
        List<String> list = lc22.generateParenthesis(3);
        for (String s : list) {
            System.out.println(s);
        }
    }

    public List<String> generateParenthesis(int n) {
        // 结果
        List<String> result = new ArrayList<>();

        // 生成括号
        generateAllBracket(result, new StringBuilder(), n * 2, 0);

        return result;
    }

    private void generateAllBracket(List<String> result, StringBuilder bracketString, int n, int leftCount) {
        if (bracketString.length() == n) {
            result.add(bracketString.toString());
            return;
        }

        if (n - bracketString.length() > leftCount) {
            bracketString.append("(");
            generateAllBracket(result, bracketString, n, leftCount + 1);
            bracketString.deleteCharAt(bracketString.length() - 1);
        }

        if (leftCount > 0) {
            bracketString.append(')');
            generateAllBracket(result, bracketString, n, leftCount - 1);
            bracketString.deleteCharAt(bracketString.length() - 1);
        }
    }

}
